package 链表;

import java.util.Stack;

/**
 * https://leetcode-cn.com/leetbook/read/linked-list/fov6t/
 *
 * 给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。
 */
public class 回文链表 {
    public class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }

    //使用栈做
    public boolean isPalindromeStack(ListNode head) {
        if(head == null) return false;
        ListNode tmp = head;
        Stack<Integer> stack = new Stack<>();
        int len = 0;
        while(tmp!=null){ //将节点全部入栈
            stack.push(tmp.val);
            tmp = tmp.next;
            len++;
        }
        //只需要比较前半部分和后半部分
        len >>= 1;
        while(len-- >= 0){
            if(head.val != stack.pop()){
                return false;
            }
            head = head.next;
        }
        return true;
    }

    public boolean isPalindrome(ListNode head) {
        if(head == null) return false;

        int size = size(head);
        ListNode tmp = head;
        ListNode[] nodes = new ListNode[size];
        for (int i = 0; i < nodes.length; i++) {
            nodes[i] = tmp;
            tmp = tmp.next;
        }

        for(int i=0;i< nodes.length/2;++i){
            if(nodes[i].val != nodes[nodes.length-i-1].val){
                return false;
            }
        }
        return true;
    }

    private int size(ListNode head){
        if(head == null) return 0;
        int size = 0;
        ListNode tmp = head;
        while(tmp!=null){
            size++;
            tmp = tmp.next;
        }
        return size;
    }
}
